package LC.question1_100;

import java.util.ArrayList;

/**
 * @author lhn
 * @date 2024-09-17 13:31
 */

public class Q004 {
    public static void main(String[] args) {
//        int[] nums1 = {1, 3};
//        int[] nums2 = {2};
//        System.out.println(findMedianSortedArrays(nums1, nums2));

        int[] nums3 = {2, 2, 4, 4};
        int[] nums4 = {2, 2, 2, 4, 4};
        System.out.println(findMedianSortedArrays(nums3, nums4));
    }

    //  方法一，合并数组，再计算中位数
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len1Index = 0;
        int len2Index = 0;
        ArrayList<Integer> list = new ArrayList<>();
        while (list.size() < len1 + len2) {
            if (len1Index < len1 && len2Index < len2) {
                if (nums1[len1Index] < nums2[len2Index]) {
                    list.add(nums1[len1Index]);
                    len1Index ++;
                } else {
                    list.add(nums2[len2Index]);
                    len2Index ++;
                }
            } else if (len1Index < len1) {
                list.add(nums1[len1Index]);
                len1Index ++;
            } else if (len2Index < len2) {
                list.add(nums2[len2Index]);
                len2Index ++;
            }
        }
        if (list.size() % 2 == 0 ) {
            //  偶数返回 n / 2 - 1 和 n / 2 的平均值
            return (list.get(list.size() / 2 - 1) + list.get(list.size() / 2)) / 2.0;
        } else {
            //  奇数返回 n / 2 的值
            return list.get(list.size() / 2);
        }
    }

    //  方法二，双指针，找到中位数
}
